#define _CRT_SECURE_NO_WARNINGS 1

#include <string>
using namespace std;

class Solution {
public:
    string addBinary(string a, string b) {
        string ret;
        int ai = a.size() - 1;
        int bi = b.size() - 1;
        int carry = 0;
        while (ai >= 0 || bi >= 0 || carry)
        {
            int num1 = ai >= 0 ? a[ai--] - '0' : 0;
            int num2 = bi >= 0 ? b[bi--] - '0' : 0;
            int sum = (num1 + num2 + carry) % 2;
            carry = (num1 + num2 + carry) / 2;
            ret += sum + '0';
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};